/**
 * 背包问题
 * 在给定空间的情况下，给了一堆物品，看看拿哪些能获得最大收益
 */

//  474. 一和零
function findMaxForm(strs: string[], m: number, n: number): number {
    //* 给定空间 m*n
    //* 给定了一些物品strs 
    //* 要求长度最大
    //* 背包问题
    const len = strs.length
    const dp = new Array(len+1).fill(0).map(e=>new Array(m+1).fill(0).map(e=>new Array(n+1).fill(0)))
    for(let l=1;l<=len;l++){
        for(let i=0;i<=m;i++){
            for(let j=0;j<=n;j++){
                let str = strs[l-1]
                let one = 0
                let zero =0
                while(str.length>0){

                    if(str[str.length-1]=='0') zero++
                    else one++
                    str= str.substring(0,str.length-1)
                }
                if(one>j||zero>i) dp[l][i][j] = dp[l-1][i][j] 
                //* 可以压缩一维
                else dp[l][i][j] = Math.max(dp[l-1][i][j],dp[l-1][i-zero][j-one]+1)
            }
        }
    }
    return dp[len][m][n]
};


//416. 分割等和子集

//* 虽然不是bag 但挺有意思的 494. 目标和

// 518. 零钱兑换 II
function change(amount: number, coins: number[]): number {
    const len = coins.length
    const dp = new Array(len+1).fill(0).map(e=>new Array(amount+1).fill(0))
    dp[0][0]=1
    //* 可优化
    for(let i=1;i<=len;i++){
        for(let j=0;j<=amount;j++){
            for(let k=0;k*coins[i-1]<=j;k++){
                dp[i][j] +=dp[i-1][j-k*coins[i-1]] 
            }
        }
    }
    return dp[len][amount]
};


// 377. 组合总和 Ⅳ


//! 考虑顺序的版本  => 完全背包
function combinationSum4_Distinct(nums: number[], target: number): number {
    const row = nums.length
    const dp = new Array(row+1).fill(0).map(e=>new Array(target+1).fill(0))
    for(let i =0;i<=row;i++){
        dp[i][0]=1
    }
    for(let i=1;i<=row;i++){
        for(let j=1;j<=target;j++){
            let k =0
            while(j-nums[i-1]*k>=0){
                dp[i][j]+=dp[i-1][j-nums[i-1]*k]
                k++
            }
        }
    }
    return dp[row][target]
};

// 不考虑顺序的版本
function combinationSum4(nums: number[], target: number): number {
    const row = nums.length
    const dp = new Array(target+1).fill(0)
    dp[0] = 1
    for(let j=1;j<=target;j++){
        for(let i=0;i<row;i++){
            const m = j-nums[i]
            m>=0 && (dp[j]+=dp[m])
        }
    }
    return dp[target]
};

/**
 * 这个题和兑换零钱的好像
 */